/*
 * IM - Image I/O Library
 * Copyright (c) 1996 CENPES/Petrobras, TeCGraf/PUC-Rio.
 * Antonio E. Scuri - scuri@tecgraf.puc-rio.br
 * 
 * IMGIF.C
 * 
 * Contains the implementation of the GIF file format functions.
 * Part of the code is based on decompression rotines implemented by Gershon Elber on the GifLib.
 *
 * History:
 *          1996.04.05 - Changed the structure of the module to the new format.
 *          1996.06.14 - Finished inicial version.
 *
 */

#include "im.h"
#include "imio.h"
#include "imgif.h"
#include "binfile.h"


#include <stdlib.h>
#include <memory.h>
#include <string.h>


/* Gif Color Type */
/* 1 Red */
/* 1 Green */
/* 1 Blue */
/* 3 */


static int InterlacedOffset[4] = { 0, 4, 2, 1 }, /* The way Interlaced image should */
	         InterlacedJumps[4] = { 8, 8, 4, 2 };  /* be read - offsets and jumps... */


#define GIF_STAMP	  "GIF"	 /* First chars in file - GIF stamp. */
#define GIF_VERSION	"89a"	 /* First chars in file - GIF stamp. */
 
#define GIF_LZ_BITS		12

#define GIF_LZ_MAX_CODE	    4095		/* Biggest code possible in 12 bits. */
#define GIF_FLUSH_OUTPUT		4096    /* Impossible code, to signal flush. */
#define GIF_FIRST_CODE		  4097    /* Impossible code, to signal first. */
#define GIF_NO_SUCH_CODE		4098    /* Impossible code, to signal empty. */

#define GIF_HT_KEY_MASK		0x1FFF		/* 13bits keys */
#define GIF_HT_KEY_NUM_BITS		13		/* 13bits keys */
#define GIF_HT_MAX_KEY		  8191	  /* 13bits - 1, maximal code possible */
#define GIF_HT_SIZE			    8192	  /* 12bits = 4096 or twice as big! */

/* The 32 bits of the long are divided into two parts for the key & code:   */
/* 1. The code is 12 bits as our compression algorithm is limited to 12bits */
/* 2. The key is 12 bits Prefix code + 8 bit new char or 20 bits.	    */
#define GIF_HT_GET_KEY(l)	(l >> 12)
#define GIF_HT_GET_CODE(l)	(l & 0x0FFF)
#define GIF_HT_PUT_KEY(l)	(l << 12)
#define GIF_HT_PUT_CODE(l)	(l & 0x0FFF)


typedef struct _imFileGIF
{
  binFile* file_bin;     /* the binary file handle */
  int colors_offset,     /* color map offset */
      compress_lzw,      /* compress using LZW, must have licence from Unisys */
      offset,            /* image offset */
      step,              /* interlaced step */
      interlaced,        /* image is interlaced or not */
	    ClearCode,				 /* The CLEAR LZ code. */
    	BitsPerPixel,	     /* Bits per pixel (Codes uses at list this + 1). */
	    EOFCode,				   /* The EOF LZ code. */
	    RunningCode,		   /* The next code algorithm can generate. */
	    RunningBits,       /* The number of bits required to represent RunningCode. */
	    MaxCode1,          /* 1 bigger than max. possible code, in RunningBits bits. */
	    LastCode,		       /* The code before the current code. */
	    CrntCode,				   /* Current algorithm code. */
	    StackPtr,		       /* For character stack (see below). */
	    CrntShiftState;		 /* Number of bits in CrntShiftDWord. */
  unsigned char Buf[256];	                  /* Compressed input is buffered here. */
  unsigned long CrntShiftDWord;             /* For bytes decomposition into codes. */
  unsigned char Stack[GIF_LZ_MAX_CODE];	    /* Decoded pixels are stacked here. */
  unsigned char Suffix[GIF_LZ_MAX_CODE+1];	/* So we can trace the codes. */
  unsigned int Prefix[GIF_LZ_MAX_CODE+1];
  unsigned long HTable[GIF_HT_SIZE];            /* hash table for the compression */
} imFileGIF;

static imGifTranspIndex transp_index_cb = NULL;

/******************************************************************************
* Routine to generate an HKey for the hashtable out of the given unique key.  *
* The given Key is assumed to be 20 bits as follows: lower 8 bits are the     *
* new postfix character, while the upper 12 bits are the prefix code.	      *
* Because the average hit ratio is only 2 (2 hash references per entry),      *
* evaluating more complex keys (such as twin prime keys) does not worth it!   *
******************************************************************************/
static int imGIFHashKeyItem(unsigned long Item)
{
  return ((Item >> 12) ^ Item) & GIF_HT_KEY_MASK;
}


/******************************************************************************
* Routine to insert a new Item into the HashTable. The data is assumed to be  *
* new one.								      *
******************************************************************************/
void imGIFInsertHashTable(unsigned long *HTable, unsigned long Key, int Code)
{
  int HKey = imGIFHashKeyItem(Key);

  while (GIF_HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) 
  {
    HKey = (HKey + 1) & GIF_HT_KEY_MASK;
  }

  HTable[HKey] = GIF_HT_PUT_KEY(Key) | GIF_HT_PUT_CODE(Code);
}


/******************************************************************************
* Routine to test if given Key exists in HashTable and if so returns its code *
* Returns the Code if key was found, -1 if not.				      *
******************************************************************************/
int imGIFExistsHashTable(unsigned long *HTable, unsigned long Key)
{
  int HKey = imGIFHashKeyItem(Key);
  unsigned long HTKey;

  while ((HTKey = GIF_HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) 
  {
    if (Key == HTKey) 
      return GIF_HT_GET_CODE(HTable[HKey]);

    HKey = (HKey + 1) & GIF_HT_KEY_MASK;
  }

  return -1;
}


/******************************************************************************
*   This routines buffers the given characters until 255 characters are ready *
* to be output. If Code is equal to -1 the buffer is flushed (EOF).	      *
*   The buffer is Dumped with first byte as its size, as GIF format requires. *
*   Returns GIF_OK if written succesfully.				      *
******************************************************************************/
static int imGIFBufferedOutput(binFile* file_bin, unsigned char *Buf, int c)
{
  if (c == GIF_FLUSH_OUTPUT) 
  {
    /* Flush everything out. */
    if (Buf[0] != 0)
      binFileWrite1ByteBuf(file_bin, Buf, Buf[0] + 1);

    /* Mark end of compressed data, by an empty block (see GIF doc): */
    Buf[0] = 0;
    binFileWrite1ByteBuf(file_bin, Buf, 1);
  }
  else 
  {
    if (Buf[0] == 255) 
    {
      /* Dump out this buffer - it is full: */
      binFileWrite1ByteBuf(file_bin, Buf, Buf[0] + 1);
      Buf[0] = 0;
    }

  Buf[++Buf[0]] = (unsigned char)c;
  }

  if (binFileError(file_bin))
    return IM_ERR_WRITE;

  return IM_ERR_NONE;
}


/******************************************************************************
*   The LZ compression output routine:					      *
*   This routine is responsable for the compression of the bit stream into    *
* 8 bits (bytes) packets.						      *
*   Returns GIF_OK if written succesfully.				      *
******************************************************************************/
static int imGIFCompressOutput(imFileGIF* file_gif, int Code)
{
  binFile* file_bin = file_gif->file_bin;
  int err = IM_ERR_NONE;

  if (Code == GIF_FLUSH_OUTPUT) 
  {
    while (file_gif->CrntShiftState > 0) 
    {
      /* Get Rid of what is left in DWord, and flush it. */
      err = imGIFBufferedOutput(file_bin, file_gif->Buf, file_gif->CrntShiftDWord & 0xff);
      file_gif->CrntShiftDWord >>= 8;
      file_gif->CrntShiftState -= 8;
    }
    file_gif->CrntShiftState = 0;			   /* For next time. */
    err = imGIFBufferedOutput(file_bin, file_gif->Buf, GIF_FLUSH_OUTPUT);
  }
  else 
  {
    file_gif->CrntShiftDWord |= ((long) Code) << file_gif->CrntShiftState;
    file_gif->CrntShiftState += file_gif->RunningBits;
    while (file_gif->CrntShiftState >= 8) 
    {
      /* Dump out full bytes: */
      err = imGIFBufferedOutput(file_bin, file_gif->Buf, file_gif->CrntShiftDWord & 0xff);
      file_gif->CrntShiftDWord >>= 8;
      file_gif->CrntShiftState -= 8;
    }
  }

  if (file_gif->compress_lzw)
  {
    /* If code cannt fit into RunningBits bits, must raise its size. Note */
    /* however that codes above 4095 are used for special signaling.      */
    if (file_gif->RunningCode >= file_gif->MaxCode1 && Code <= GIF_LZ_MAX_CODE) 
    {
      file_gif->MaxCode1 = 1 << ++file_gif->RunningBits;
    }
  }

  return err;
}

/******************************************************************************
*   The LZ compression routine:						      *
*   This version compress the given buffer Line of length LineLen.	      *
*   This routine can be called few times (one per scan line, for example), in *
* order the complete the whole image.					      *
******************************************************************************/
static int imGIFCompressLineLZW(imFileGIF* file_gif, unsigned char *Line, int LineLen)
{
  int i = 0, CrntCode, NewCode;
  unsigned long NewKey;
  unsigned char Pixel;

  if (file_gif->CrntCode == GIF_FIRST_CODE)		  /* Its first time! */
    CrntCode = Line[i++];
  else
    CrntCode = file_gif->CrntCode;     /* Get last code in compression. */

  while (i < LineLen) 
  {			    /* Decode LineLen items. */
    Pixel = Line[i++];		      /* Get next pixel from stream. */
    /* Form a new unique key to search hash table for the code combines  */
    /* CrntCode as Prefix string with Pixel as postfix char.	     */
    NewKey = (((unsigned long) CrntCode) << 8) + Pixel;

    if ((NewCode = imGIFExistsHashTable(file_gif->HTable, NewKey)) >= 0) 
    {
      /* This Key is already there, or the string is old one, so	     */
      /* simple take new code as our CrntCode:			     */
      CrntCode = NewCode;
    }
    else 
    {
      /* Put it in hash table, output the prefix code, and make our    */
      /* CrntCode equal to Pixel.					     */
      if (imGIFCompressOutput(file_gif, CrntCode) != IM_ERR_NONE) 
        return IM_ERR_WRITE;

      CrntCode = Pixel;

      /* If however the HashTable if full, we send a clear first and   */
      /* Clear the hash table.					     */
      if (file_gif->RunningCode >= GIF_LZ_MAX_CODE) 
      {
        /* Time to do some clearance: */
        if (imGIFCompressOutput(file_gif, file_gif->ClearCode) != IM_ERR_NONE) 
          return IM_ERR_WRITE;

        file_gif->RunningCode = file_gif->EOFCode + 1;
        file_gif->RunningBits = file_gif->BitsPerPixel + 1;
        file_gif->MaxCode1 = 1 << file_gif->RunningBits;
        memset(file_gif->HTable, 0xFF, GIF_HT_SIZE * sizeof(long));
      }
      else 
      {
        /* Put this unique key with its relative Code in hash table: */
        imGIFInsertHashTable(file_gif->HTable, NewKey, file_gif->RunningCode++);
      }
    }
  }

  /* Preserve the current state of the compression algorithm: */
  file_gif->CrntCode = CrntCode;

  return IM_ERR_NONE;
}

/******************************************************************************
*   The fake compression routine:						      *
*   This version compress the given buffer Line of length LineLen.	      *
*   This routine can be called few times (one per scan line, for example), in *
* order the complete the whole image.					      *
******************************************************************************/
static int imGIFCompressLine(imFileGIF* file_gif, unsigned char *Line, int LineLen)
{
  int i = 0, CrntCode;
  unsigned char Pixel;

  if (file_gif->CrntCode == GIF_FIRST_CODE)		  /* Its first time! */
    CrntCode = Line[i++];
  else
    CrntCode = file_gif->CrntCode;     /* Get last code in compression. */

  while (i < LineLen) 
  {			    /* Decode LineLen items. */
    Pixel = Line[i++];		      /* Get next pixel from stream. */

    if (imGIFCompressOutput(file_gif, CrntCode) != IM_ERR_NONE) 
      return IM_ERR_WRITE;

    file_gif->RunningCode++;
    CrntCode = Pixel;

    if (file_gif->RunningCode >= (1 << (file_gif->BitsPerPixel)) - 2) 
    {
      if (imGIFCompressOutput(file_gif, file_gif->ClearCode) != IM_ERR_NONE) 
        return IM_ERR_WRITE;

      file_gif->RunningCode = 0;
    }
  }

  /* Preserve the current state of the compression algorithm: */
  file_gif->CrntCode = CrntCode;

  return IM_ERR_NONE;
}


/******************************************************************************
*   This routines read one gif data block at a time and buffers it internally *
* so that the decompression routine could access it.			      *
*   The routine returns the next byte from its internal buffer (or read next  *
* block in if buffer empty) and returns GIF_OK if succesful.		      *
******************************************************************************/
static int imGIFBufferedInput(binFile* file_bin, unsigned char *Buf, unsigned char *NextByte)
{
  if (Buf[0] == 0) 
  {
    /* Needs to read the next buffer - this one is empty: */
    binFileRead1ByteBuf(file_bin, Buf, 1);
    binFileRead1ByteBuf(file_bin, &Buf[1], Buf[0]);

    if (binFileError(file_bin))
      return IM_ERR_READ;

    *NextByte = Buf[1];
    Buf[1] = 2;	   /* We use now the second place as last char read! */
    Buf[0]--;
  }
  else 
  {
    *NextByte = Buf[Buf[1]++];
    Buf[0]--;
  }

  return IM_ERR_NONE;
}

/******************************************************************************
*   The LZ decompression input routine:					      *
*   This routine is responsable for the decompression of the bit stream from  *
* 8 bits (bytes) packets, into the real codes.				      *
*   Returns GIF_OK if read succesfully.					      *
******************************************************************************/
static int imGIFDecompressInput(imFileGIF* file_gif, int *Code)
{
  binFile* file_bin = file_gif->file_bin;
  unsigned char NextByte;
  static unsigned int CodeMasks[] = 
  {
    0x0000, 0x0001, 0x0003, 0x0007,
    0x000f, 0x001f, 0x003f, 0x007f,
    0x00ff, 0x01ff, 0x03ff, 0x07ff,
    0x0fff
  };

  while (file_gif->CrntShiftState < file_gif->RunningBits) 
  {
    /* Needs to get more bytes from input stream for next code: */
    if (imGIFBufferedInput(file_bin, file_gif->Buf, &NextByte) != IM_ERR_NONE) 
      return IM_ERR_READ;

    file_gif->CrntShiftDWord |= ((unsigned long) NextByte) << file_gif->CrntShiftState;
    file_gif->CrntShiftState += 8;
  }

  *Code = file_gif->CrntShiftDWord & CodeMasks[file_gif->RunningBits];

  file_gif->CrntShiftDWord >>= file_gif->RunningBits;
  file_gif->CrntShiftState -= file_gif->RunningBits;

  /* If code cannt fit into RunningBits bits, must raise its size. Note */
  /* however that codes above 4095 are used for special signaling.      */
  if (++(file_gif->RunningCode) > file_gif->MaxCode1 && file_gif->RunningBits < GIF_LZ_BITS) 
  {
    file_gif->MaxCode1 <<= 1;
    file_gif->RunningBits++;
  }

  return IM_ERR_NONE;
}

/******************************************************************************
* Routine to trace the Prefixes linked list until we get a prefix which is    *
* not code, but a pixel value (less than ClearCode). Returns that pixel value.*
* If image is defective, we might loop here forever, so we limit the loops to *
* the maximum possible if image O.k. - LZ_MAX_CODE times.		      *
******************************************************************************/
static int imGIFGetPrefixChar(unsigned int *Prefix, int Code, int ClearCode)
{
  int i = 0;

  while (Code > ClearCode && i++ <= GIF_LZ_MAX_CODE) 
    Code = Prefix[Code];

  return Code;
}

static int imGIFDecompressLine(imFileGIF* file_gif, unsigned char *Line,	int LineLen)
{
  int i = 0, j, CrntCode, EOFCode, ClearCode, CrntPrefix, LastCode, StackPtr;
  unsigned char *Stack, *Suffix;
  unsigned int *Prefix;

  StackPtr = file_gif->StackPtr;
  Prefix = file_gif->Prefix;
  Suffix = file_gif->Suffix;
  Stack = file_gif->Stack;
  EOFCode = file_gif->EOFCode;
  ClearCode = file_gif->ClearCode;
  LastCode = file_gif->LastCode;

  if (StackPtr != 0) 
  {
    /* Let pop the stack off before continueing to read the gif file: */
    while (StackPtr != 0 && i < LineLen) 
      Line[i++] = Stack[--StackPtr];
  }

  while (i < LineLen) 
  {			    
    /* Decode LineLen items. */
    if (imGIFDecompressInput(file_gif, &CrntCode))
      return IM_ERR_READ;

    if (CrntCode == EOFCode) 
    {
      /* Note however that usually we will not be here as we will stop */
      /* decoding as soon as we got all the pixel, or EOF code will    */
      /* not be read at all, and DGifGetLine/Pixel clean everything.   */
      if (i != LineLen - 1) 
        return IM_ERR_READ;
  
    i++;
    }
    else if (CrntCode == ClearCode) 
    {
      /* We need to start over again: */
      for (j = 0; j <= GIF_LZ_MAX_CODE; j++) 
        Prefix[j] = GIF_NO_SUCH_CODE;

      file_gif->RunningCode = file_gif->EOFCode + 1;
      file_gif->RunningBits = file_gif->BitsPerPixel + 1;
      file_gif->MaxCode1 = 1 << file_gif->RunningBits;
      LastCode = file_gif->LastCode = GIF_NO_SUCH_CODE;
    }
    else 
    {
      /* Its regular code - if in pixel range simply add it to output  */
      /* stream, otherwise trace to codes linked list until the prefix */
      /* is in pixel range:					     */
      if (CrntCode < ClearCode) 
      {
        /* This is simple - its pixel scalar, so add it to output:   */
        Line[i++] = (unsigned char)CrntCode;
      }
      else 
      {
        /* Its a code to needed to be traced: trace the linked list  */
        /* until the prefix is a pixel, while pushing the suffix     */
        /* pixels on our stack. If we done, pop the stack in reverse */
        /* (thats what stack is good for!) order to output.	     */
        if (Prefix[CrntCode] == GIF_NO_SUCH_CODE) 
        {
          /* Only allowed if CrntCode is exactly the running code: */
          /* In that case CrntCode = XXXCode, CrntCode or the	     */
          /* prefix code is last code and the suffix char is	     */
          /* exactly the prefix of last code!			     */
          if (CrntCode == file_gif->RunningCode - 2) 
          {
            CrntPrefix = LastCode;
            Suffix[file_gif->RunningCode - 2] =
            Stack[StackPtr++] = (unsigned char)imGIFGetPrefixChar(Prefix, LastCode, ClearCode);
          }
          else 
            return IM_ERR_READ;
        }
        else
          CrntPrefix = CrntCode;

        /* Now (if image is O.K.) we should not get an NO_SUCH_CODE  */
        /* During the trace. As we might loop forever, in case of    */
        /* defective image, we count the number of loops we trace    */
        /* and stop if we got LZ_MAX_CODE. obviously we can not      */
        /* loop more than that.					     */
        j = 0;
        while (j++ <= GIF_LZ_MAX_CODE && CrntPrefix > ClearCode && CrntPrefix <= GIF_LZ_MAX_CODE) 
        {
          Stack[StackPtr++] = Suffix[CrntPrefix];
          CrntPrefix = Prefix[CrntPrefix];
        }

        if (j >= GIF_LZ_MAX_CODE || CrntPrefix > GIF_LZ_MAX_CODE) 
            return IM_ERR_READ;

        /* Push the last character on stack: */
        Stack[StackPtr++] = (unsigned char)CrntPrefix;

        /* Now lets pop all the stack into output: */
        while (StackPtr != 0 && i < LineLen)
          Line[i++] = Stack[--StackPtr];
      }

      if (LastCode != GIF_NO_SUCH_CODE) 
      {
        Prefix[file_gif->RunningCode - 2] = LastCode;

        if (CrntCode == file_gif->RunningCode - 2) 
        {
          /* Only allowed if CrntCode is exactly the running code: */
          /* In that case CrntCode = XXXCode, CrntCode or the	     */
          /* prefix code is last code and the suffix char is	     */
          /* exactly the prefix of last code!			     */
          Suffix[file_gif->RunningCode - 2] = (unsigned char)imGIFGetPrefixChar(Prefix, LastCode, ClearCode);
        }
        else 
        {
          Suffix[file_gif->RunningCode - 2] = (unsigned char)imGIFGetPrefixChar(Prefix, CrntCode, ClearCode);
        }
      }
    
      LastCode = CrntCode;
    }
  }

  file_gif->LastCode = LastCode;
  file_gif->StackPtr = StackPtr;

  return IM_ERR_NONE;
}


static imFile* imGIFReadOpen(char* filename, int *err)
{
  int found_image = 0, i;
  char stamp[4];
  unsigned short word_value;
  unsigned char byte_value;
  imFile *ifile = (imFile*)malloc(sizeof(imFile));
  imFileGIF *file_gif = (imFileGIF*)malloc(sizeof(imFileGIF));
  binFile* file_bin;

  ifile->file = file_gif;

  /* opens the binary file for reading with intel byte order */
  file_bin = binFileOpen(filename, 0, 0);
  if (file_bin == NULL)
  {
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_OPEN;
    return NULL;
  }

  file_gif->file_bin = file_bin;

  /* reads the GIF format identifier */
  binFileRead1ByteBuf(file_bin, (unsigned char*)stamp, 3);
  if (binFileError(file_bin))
  {
    binFileClose(file_bin);
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_READ;
    return NULL;
  }

  /* the stamp is a string */
  stamp[3] = 0;
  if (strstr(stamp, GIF_STAMP) == NULL)
  {
    binFileClose(file_bin);
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_FORMAT;
    return NULL;
  }

  /* image is always map */
  ifile->type = IM_MAP;

  /* image is always compressed */
  ifile->compress = IM_DEFAULT;

  /* jump 3+4 bytes */
  binFileSeekOffset(file_bin, 3+4);

  /* reads the screen information byte */
  binFileRead1ByteBuf(file_bin, &byte_value, 1);

  /* jump 2 bytes */
  binFileSeekOffset(file_bin, 2);

  /* if we have a global color map */
  if (byte_value & 0x80)
  {
    int bpp = (byte_value & 0x07) + 1;
    ifile->pal_size = 1 << bpp;
    file_gif->colors_offset = binFileTell(file_bin);

    /* skip the color map */
    binFileSeekOffset(file_bin, 3*ifile->pal_size);
  }
  else
    file_gif->colors_offset = 0;

  /* reads image information in the respective record type, skip the others */
  do
  {
    /* reads the record type byte */
    binFileRead1ByteBuf(file_bin, &byte_value, 1);

    switch (byte_value) 
    {
	  case ',':
      /* jump 4 bytes */
      binFileSeekOffset(file_bin, 4);

      /* reads the image width */
      binFileRead2BytesBuf(file_bin, &word_value, 1);
      ifile->width = word_value;

      /* reads the image height */
      binFileRead2BytesBuf(file_bin, &word_value, 1);
      ifile->height = word_value;

      /* reads the image information byte */
      binFileRead1ByteBuf(file_bin, &byte_value, 1);

      file_gif->interlaced = byte_value & 0x40;

      if (byte_value & 0x80)
      {
        int bpp = (byte_value & 0x07) + 1;
        ifile->pal_size = 1 << bpp;
        file_gif->colors_offset = binFileTell(file_bin);

        /* skip the color map */
        binFileSeekOffset(file_bin, 3*ifile->pal_size);
      }

      /* we will read only this image, so break te switch and the loop */
      found_image = 1;
	    break;
	  case '!':
      /* jump 1 byte */
      binFileSeekOffset(file_bin, 1);

      /* skip each extension block */
      do
      {
        /* reads the number of bytes of that extension */
        binFileRead1ByteBuf(file_bin, &byte_value, 1);

        if (binFileError(file_bin))
        {
          binFileClose(file_bin);
          free(file_gif);
          free(ifile);
          if (err) *err = IM_ERR_FORMAT;
          return NULL;
        }

        /* jump number of bytes, ignores the contents */
        if (byte_value) binFileSeekOffset(file_bin, byte_value);
      }while (byte_value != 0);

	    break;
	  case ';':
	  default:
      binFileClose(file_bin);
      free(file_gif);
      free(ifile);
      if (err) *err = IM_ERR_FORMAT;
      return NULL;
	  }
  } while (!found_image || binFileEndOfFile(file_bin));


  if (binFileError(file_bin) || !found_image || file_gif->colors_offset == 0)
  {
    binFileClose(file_bin);
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_READ;
    return NULL;
  }

  /* reads the code byte */
  binFileRead1ByteBuf(file_bin, &byte_value, 1);

  /* now initialize the compression control data */

  file_gif->BitsPerPixel = byte_value;
  file_gif->ClearCode = (1 << byte_value);
  file_gif->EOFCode = file_gif->ClearCode + 1;
  file_gif->RunningCode = file_gif->EOFCode + 1;
  file_gif->RunningBits = byte_value + 1;	 /* Number of bits per code. */
  file_gif->MaxCode1 = 1 << file_gif->RunningBits;     /* Max. code + 1. */
  file_gif->StackPtr = 0;		    /* No pixels on the pixel stack. */
  file_gif->LastCode = GIF_NO_SUCH_CODE;
  file_gif->CrntShiftState = 0;	/* No information in CrntShiftDWord. */
  file_gif->CrntShiftDWord = 0;
  file_gif->Buf[0] = 0;			      /* Input Buffer empty. */

  for (i = 0; i <= GIF_LZ_MAX_CODE; i++) 
    file_gif->Prefix[i] = GIF_NO_SUCH_CODE;

  /* now initialize the imFile control data */

  ifile->split = 0;     /* image is RGB packed */
  ifile->planes[0] = 0; /* sets the default plane order since split = 0 */
  ifile->planes[1] = 1;
  ifile->planes[2] = 2;
  ifile->pre_colors = 1;  /* color map is before the image */

  file_gif->offset = binFileTell(file_bin);

  file_gif->step = 0;

	if (file_gif->interlaced)
    ifile->cur_line = (ifile->height - 1) - InterlacedOffset[0];
	else
    ifile->cur_line = (ifile->height - 1);

  if (err) *err = IM_ERR_NONE;

  return ifile;
}

static void imGIFWriteGraphicsControl(binFile* file_bin, unsigned char transparency_index)
{
  unsigned short word_value;
  unsigned char byte_value;

  /* record type byte */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)"!", 1);

  /* block label */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)"\xF9", 1);

  /* block size */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)"\x04", 1);

  /* transparency flag */
  byte_value = 0x01;
  binFileWrite1ByteBuf(file_bin, &byte_value, 1);

  /* delay time */
  word_value = 0;
  binFileWrite1ByteBuf(file_bin, (unsigned char*)&word_value, 2);

  /* transparency color */
  binFileWrite1ByteBuf(file_bin, &transparency_index, 1);

  /* terminator */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)"\0", 1);
}

static imFile* imGIFWriteOpen(char* filename, int width, int height, int type, int compress, int pal_size, int *err)
{
  unsigned char byte_value, buf[256*3];
  unsigned short word_value;
  imFile *ifile = (imFile*)malloc(sizeof(imFile));
  imFileGIF *file_gif = (imFileGIF*)malloc(sizeof(imFileGIF));
  binFile* file_bin;

  /* can not save rgb images */
  if (type == IM_RGB)
  {
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_TYPE;
    return NULL;
  }

  ifile->file = file_gif;

  /* opens the binary file for writing with intel byte order */
  file_bin = binFileOpen(filename, 1, 0);
  if (file_bin == NULL)
  {
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_OPEN;
    return NULL;
  }

  file_gif->file_bin = file_bin;

  ifile->width = width;
  ifile->height = height;
  ifile->type = type;
  ifile->pal_size = pal_size;
  ifile->compress = compress;

  /* now initialize the imFile control data */

  ifile->split = 0;     /* image is RGB packed */
  ifile->planes[0] = 0; /* sets the default plane order since split = 0 */
  ifile->planes[1] = 1;
  ifile->planes[2] = 2;
  ifile->cur_line = ifile->height - 1;  /* first line */
  ifile->pre_colors = 1;  /* color map is before the image */

  file_gif->step = 0;          /* interlaced step */
  file_gif->interlaced = 0;    /* image is not interlaced */
  file_gif->compress_lzw = 0;  /* default is not to use LZW */

  if (ifile->compress == IM_COMPRESSED)
    file_gif->compress_lzw = 1;

  if (file_gif->compress_lzw)
  {
    /* initializes the hash table */
    memset(file_gif->HTable, 0xFF, GIF_HT_SIZE * sizeof(long));
  }

  /* writes the GIF STAMP */

  binFileWrite1ByteBuf(file_bin, (unsigned char*)GIF_STAMP, 3); /* identifier */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)GIF_VERSION, 3); /* format version */

  /* writes the GIF screen information */

  word_value = (unsigned short)ifile->width;
  binFileWrite2BytesBuf(file_bin, &word_value, 1); /* screen=image width */
  word_value = (unsigned short)ifile->height;
  binFileWrite2BytesBuf(file_bin, &word_value, 1); /* screen=image height */

  byte_value = 0x80 | ((8 - 1) << 4) | (8 - 1);
  binFileWrite1ByteBuf(file_bin, &byte_value, 1); /* screen information */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)"\0\0", 2);     

  file_gif->colors_offset = binFileTell(file_bin);     /* color map offset */
  /* skip the color map */
  binFileWrite1ByteBuf(file_bin, buf, 256*3);  

  /* writes the transparency */     
  if (transp_index_cb)
  {
    unsigned char transp_index = 0;
    transp_index_cb(filename, &transp_index);
    imGIFWriteGraphicsControl(file_bin, transp_index);
  }

  /* writes the GIF image information */
  binFileWrite1ByteBuf(file_bin, (unsigned char*)",", 1);  /* Image seperator character. */
  word_value = 0;
  binFileWrite2BytesBuf(file_bin, &word_value, 1); /* image left */
  binFileWrite2BytesBuf(file_bin, &word_value, 1); /* image top */
  word_value = (unsigned short)ifile->width;
  binFileWrite2BytesBuf(file_bin, &word_value, 1); /* image width */
  word_value = (unsigned short)ifile->height;
  binFileWrite2BytesBuf(file_bin, &word_value, 1); /* image height */
  byte_value = 0x00 | 0x00 | (8 - 1);
  binFileWrite1ByteBuf(file_bin, &byte_value, 1); /* image information */

  /* initializes compression data */

  byte_value = 8;
  binFileWrite1ByteBuf(file_bin, &byte_value, 1); /* Write the Code size to file. */

  file_gif->Buf[0] = 0;			  /* Nothing was output yet. */
  file_gif->BitsPerPixel = 8;
  file_gif->ClearCode = (1 << 8);
  file_gif->EOFCode = file_gif->ClearCode + 1;
  file_gif->RunningBits = 8 + 1;	 /* Number of bits per code. */
  file_gif->MaxCode1 = 1 << file_gif->RunningBits;	   /* Max. code + 1. */
  file_gif->CrntCode = GIF_FIRST_CODE;	   /* Signal that this is first one! */
  file_gif->CrntShiftState = 0;      /* No information in CrntShiftDWord. */
  file_gif->CrntShiftDWord = 0;

  if (file_gif->compress_lzw)
    file_gif->RunningCode = file_gif->EOFCode + 1;
  else
    file_gif->RunningCode = 0;
  
  imGIFCompressOutput(file_gif, file_gif->ClearCode);

  file_gif->offset = binFileTell(file_bin);     /* image offset */

  /* tests if everything was ok */
  if (binFileError(file_bin))
  {
    binFileClose(file_bin);
    free(file_gif);
    free(ifile);
    if (err) *err = IM_ERR_WRITE;
    return NULL;
  }

  if (err) *err = IM_ERR_NONE;

  return ifile;
}


static void imGIFClose(imFile* ifile)
{
  imFileGIF *file_gif = (imFileGIF*)ifile->file;
  binFile* file_bin = file_gif->file_bin;

  binFileClose(file_bin);

  free(file_gif);
  free(ifile);
}


static int imGIFReadColors(imFile* ifile, long *colors)
{
  int c, i;
  unsigned char gif_colors[256 * 3];
  imFileGIF *file_gif = (imFileGIF*)ifile->file;
  binFile* file_bin = file_gif->file_bin;

  /* jump to color map offset */
  binFileSeekTo(file_bin, file_gif->colors_offset);

  /* reads the color palette */
  binFileRead1ByteBuf(file_bin, gif_colors, ifile->pal_size * 3);

  if (binFileError(file_bin))
    return IM_ERR_READ;

  /* convert the color map to the IM format */
  for (c = 0; c < ifile->pal_size; c++)
  {
    i = c * 3;
    colors[c] = imEncodeColor(gif_colors[i], gif_colors[i+1], gif_colors[i+2]);
  }

  return IM_ERR_NONE;
}


static int imGIFWriteColors(imFile* ifile, long *colors)
{
  int c, i;
  unsigned char gif_colors[256 * 3];
  imFileGIF *file_gif = (imFileGIF*)ifile->file;
  binFile* file_bin = file_gif->file_bin;

  /* jump to color map offset */
  binFileSeekTo(file_bin, file_gif->colors_offset);

  /* convert the color map to the IM format */
  for (c = 0; c < ifile->pal_size; c++)
  {
    i = c * 3; 
    imDecodeColor(&gif_colors[i], &gif_colors[i+1], &gif_colors[i+2], colors[c]);
  }

  /* writes the color palette */
  binFileWrite1ByteBuf(file_bin, gif_colors, 256 * 3);

  if (binFileError(file_bin))
    return IM_ERR_WRITE;

  return IM_ERR_NONE;
}


static int imGIFReadLine(imFile* ifile, unsigned char *map)
{
  imFileGIF *file_gif = (imFileGIF*)ifile->file;
  binFile* file_bin = file_gif->file_bin;

  /* jump to image offset */
  if (file_gif->offset)
  {
    binFileSeekTo(file_bin, file_gif->offset);
    file_gif->offset = 0;
  }

	if (file_gif->interlaced)
	{
    ifile->cur_line -= InterlacedJumps[file_gif->step];

    if (ifile->cur_line < 0)
    {
      file_gif->step++;
      ifile->cur_line = (ifile->height - 1) - InterlacedOffset[file_gif->step];
    }
	}
	else
    ifile->cur_line--;

  return imGIFDecompressLine(file_gif, map, ifile->width);
}


static int imGIFWriteLine(imFile* ifile, unsigned char *map)
{
  int err;
  imFileGIF *file_gif = (imFileGIF*)ifile->file;
  binFile* file_bin = file_gif->file_bin;

  /* jump to image offset */
  if (file_gif->offset)
  {
    binFileSeekTo(file_bin, file_gif->offset);
    file_gif->offset = 0;
  }

  if (file_gif->compress_lzw)
    err = imGIFCompressLineLZW(file_gif, map, ifile->width);
  else
    err = imGIFCompressLine(file_gif, map, ifile->width);

  /* we have just write one more line */
  ifile->cur_line--;

  /* writes the end picture code */
  if (ifile->cur_line < 0)
  {
    /* We are done - output last Code and flush output buffers: */
    imGIFCompressOutput(file_gif, file_gif->CrntCode);
    imGIFCompressOutput(file_gif, file_gif->EOFCode);
    imGIFCompressOutput(file_gif, GIF_FLUSH_OUTPUT);
      
    binFileWrite1ByteBuf(file_bin, (unsigned char*)";", 1);
  }

  return err;
}


static int imGIFRegisterCallback(imCallback cb, int id)
{
  switch(id)
  {
  case IM_GIF_TRANSPARENT_COLOR_CB:
    {
      transp_index_cb = (imGifTranspIndex)cb;
      return 1;
    }
  }

  /* callback not found */
  return 0;
}


static imFormat _imFormatGIF =
{
  0,
  imGIFRegisterCallback,
  imGIFReadOpen,
  imGIFWriteOpen,
  imGIFClose,
  imGIFReadColors,
  imGIFWriteColors,
  imGIFReadLine,
  imGIFWriteLine,
  NULL,
  NULL
};

imFormat* imFormatGIF(void)
{
  return &_imFormatGIF;
}
